package Ex1;

import java.util.*;

import sun.reflect.ReflectionFactory.GetReflectionFactoryAction;

/**
 * A linked implementation of a binary tree.
 * 
 * @version (15-11-2007)
 * @author Margrethe Dybdahl (modified by mlch)
 */
public class LinkedBinaryTree<E> implements BinaryTree<E> {
	private BTNode<E> root;
	private int size;

	/**
	 * Creates an empty LinkedBinaryTree. Time: O(1).
	 */
	public LinkedBinaryTree() {
		root = null;
		size = 0;
	}

	/**
	 * Returns whether the position is an external node. Time: O(1).<br />
	 * Requires: The position is valid.
	 */
	public boolean isExternal(Position<E> p) {
		return !isInternal(p);
	}

	/**
	 * Returns whether the position is an internal node. Time: O(1).<br />
	 * Requires: The position is valid.
	 */
	public boolean isInternal(Position<E> p) {
		return hasLeft(p) || hasRight(p);
	}

	/**
	 * Returns whether the position is the root of the binary tree. Time:
	 * O(1).<br /> Requires: The position is valid.
	 */
	public boolean isRoot(Position<E> p) {
		BTNode<E> v = checkPosition(p);
		return v == root;
	}

	/**
	 * Returns the left child of the position. Time: O(1).<br /> Requires: The
	 * position is valid and has a left child.
	 */
	public Position<E> left(Position<E> p) {
		BTNode<E> v = checkPosition(p);
		if (v.getLeft() == null)
			throw new RuntimeException(
					"The position does not have a left child.");

		return v.getLeft();
	}

	/**
	 * Returns an iterator on the binary tree. Time: O(n), n being the size of
	 * the tree.
	 */
	public Iterator<E> iterator() {
		List<E> list = new ArrayList<E>();
		makeList(list, root());
		return list.iterator();
	}

	/**
	 * Returns the father of the position. Time: O(1).<br /> Requires: The
	 * position is valid and not the root.
	 */
	public Position<E> parent(Position<E> p) {
		BTNode<E> v = checkPosition(p);
		if (v == root)
			throw new RuntimeException("The position can't be the root");

		return v.getParent();
	}

	/**
	 * Removes and returns the element at the position. Time: ??.<br />
	 * Requires: The position is valid and has at most one child.
	 */
	public E remove(Position<E> p) {
		BTNode<E> btNode = checkPosition(p);
		if (hasLeft(p) && hasRight(p))
			throw new RuntimeException("Must have only one child");

		BTNode<E> parent = btNode.getParent();
		BTNode<E> child;
		if (hasLeft(p))
			child = checkPosition(btNode.getLeft());
		else
			child = checkPosition(btNode.getRight());

		if (parent != null) {
			if (parent.getLeft() == p)
				parent.setLeft(child);
			else
				parent.setRight(child);
		}
		else
			root = child;

		child.setParent(parent);

		return btNode.element();
	}

	/**
	 * Replaces the element at the position with the specified element, and
	 * returns the replaced element. Time: O(1).<br /> Requires: The position is
	 * valid.
	 */
	public E replace(Position<E> p, E e) {
		BTNode<E> v = checkPosition(p);
		E old = v.element();
		v.setElement(e);
		return old;
	}

	/**
	 * Returns the right child of the position. Time: O(1).<br /> Requires: The
	 * position is valid and has a right child.
	 */
	public Position<E> right(Position<E> p) {
		BTNode<E> v = checkPosition(p);
		if (v.getRight() == null)
			throw new RuntimeException(
					"The position does not have a right child");

		return v.getRight();
	}

	/**
	 * Returns the root of the binary tree. Time: O(1).<br /> Requires: The
	 * binary tree is not empty.
	 */
	public Position<E> root() {
		if (root == null)
			throw new RuntimeException("The binary tree can't be empty.");

		return root;
	}

	/**
	 * Returns the sibling of the position. Time: O(1).<br /> Requires: The
	 * position is valid and has a sibling.
	 */
	public Position<E> sibling(Position<E> p) {
		if (isRoot(p))
			throw new RuntimeException("Root has no siblings");

		BTNode<E> btNode = checkPosition(p);
		BTNode<E> parent = btNode.getParent();

		if (parent.getLeft() == null || parent.getRight() == null)
			throw new RuntimeException("This position has no sibling");

		else if (parent.getLeft() != p)
			return parent.getLeft();

		else
			return parent.getRight();

	}

	/**
	 * Returns the count of nodes in the binary tree. Time: O(1).
	 */
	public int size() {
		return size;
	}

	/**
	 * Adds the element as root and returns the position of this root. Time:
	 * O(1).<br /> Requires: The binary tree is empty.
	 */
	public Position<E> addRoot(E e) {
		if (!isEmpty())
			throw new RuntimeException("The binary tree is not empty");

		root = new BTNode<E>(e, null, null, null);
		size = 1;
		return root;
	}

	/**
	 * Returns whether the tree is empty. Time:O(1).
	 */
	public boolean isEmpty() {
		return (size == 0);
	}

	/**
	 * Returns whether the position has a left child. Time: O(1).<br />
	 * Requires: The position is valid.
	 */
	public boolean hasLeft(Position<E> p) {
		BTNode<E> v = checkPosition(p);
		return v.getLeft() != null;
	}

	/**
	 * Returns whether the position has a right child. Time: O(1).<br />
	 * Requires: The position is valid.
	 */
	public boolean hasRight(Position<E> p) {
		BTNode<E> v = checkPosition(p);
		return v.getRight() != null;
	}

	/**
	 * Inserts the element as right child of the position, and returns the
	 * position of the new right child. Time: O(1).<br /> Requires: The position
	 * is valid and does not have a right child.
	 */
	public Position<E> insertRight(Position<E> p, E e) {
		BTNode<E> v = checkPosition(p);
		if (v.getRight() != null)
			throw new RuntimeException("The position can't have a right child");

		BTNode<E> n = new BTNode<E>(e, null, null, v);
		v.setRight(n);
		size++;
		return n;
	}

	/**
	 * Inserts the element as left child of the position, and returns the
	 * position of the new left child. Time: O(1).<br /> Requires: The position
	 * is valid and does not have a left child.
	 */
	public Position<E> insertLeft(Position<E> p, E e) {
		BTNode<E> v = checkPosition(p);
		if (v.getLeft() != null)
			throw new RuntimeException("The position can't have a left child");

		BTNode<E> n = new BTNode<E>(e, null, null, v);
		v.setLeft(n);
		size++;
		return n;
	}

	/**
	 * Adds the trees t1 and t2 as left and right subtree of the position. Time:
	 * O(1).<br /> Requires: The position is valid and is an external node.
	 */
	public void attach(Position<E> p, BinaryTree<E> t1, BinaryTree<E> t2) {
		BTNode<E> v = checkPosition(p);
		if (isInternal(v))
			throw new RuntimeException("The position can't have subtrees");

		if (!t1.isEmpty()) {
			BTNode<E> r1 = checkPosition(t1.root());
			v.setLeft(r1);
			r1.setParent(v);
			size += t1.size();
		}
		if (!t2.isEmpty()) {
			BTNode<E> r2 = checkPosition(t2.root());
			v.setRight(r2);
			r2.setParent(v);
			size += t2.size();
		}
	}

	private BTNode<E> checkPosition(Position<E> p) {
		if (p == null || !(p instanceof BTNode))
			throw new RuntimeException("Invalid position");

		return (BTNode<E>) p;
	}
	
	private void makeList(List<E> list, Position<E> p) {
		if (hasLeft(p))
			makeList(list, left(p));
		list.add(p.element());
		if (hasRight(p))
			makeList(list, right(p));
	}

	// Nested class that implements a node in a binary tree.
	private static class BTNode<T> implements Position<T> {
		private T element;
		private BTNode<T> left;
		private BTNode<T> right;
		private BTNode<T> parent;

		public BTNode(T element, BTNode<T> left, BTNode<T> right,
				BTNode<T> parent) {
			this.element = element;
			this.left = left;
			this.right = right;
			this.parent = parent;
		}

		public T element() {
			return element;
		}

		public void setElement(T element) {
			this.element = element;
		}

		public Position<T> getLeft() {
			return left;
		}

		public void setLeft(BTNode<T> left) {
			this.left = left;
		}

		public BTNode<T> getRight() {
			return right;
		}

		public void setRight(BTNode<T> right) {
			this.right = right;
		}

		public BTNode<T> getParent() {
			return parent;
		}

		public void setParent(BTNode<T> parent) {
			this.parent = parent;
		}
	}
}